import java.util.Arrays;

/**
 * 使用哈希桶解决哈希冲突问题
 */
public class HashBuck {
    static class Node {
        private int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }


    private static final float DEFULT_LOAD_FACTOR = 0.75f;  //散列表的负载因子在java中不能超过0.75

    Node[] array = new Node[10];  //设定数组初始值为10
    float use_size = 0.0f;

    public HashBuck() {
        array = new Node[10];
    }

    public boolean Do_load_factor() {
        return !(use_size / array.length < 0.75);
        //false：无需扩容  true：扩扩扩！！！
    }

    private void resize() {
        //如果散列表的负载因子超过0.75，必须扩容，但光扩容是不行的，需要对扩容之后的数组再重新进行一次哈希的插入
        Node[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];

            while (cur != null) {
                //重新计算新的的索引
                int newIndex = cur.key % newArray.length;

                //保存下一个节点的引用，放置丢失
                Node next = cur.next;  //每一个节点都要重新进行插入

                //将当前节点头插入到新的数组中
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;

                //更新当前节点的引用
                cur = next;
            }
        }
        array = newArray;
    }

    public void put(int key, int val) {
        if (Do_load_factor())
            resize();

        //遍历index下标的链表,判断是否存在key，存在就更新，不存在就进行尾插法
        int index = key / array.length;
        Node cur = array[index];
        Node prev = null;
        while (cur != null) {
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
        //链表遍历完成，没有找到这个key，进行尾插
        Node newNode = new Node(key, val);
        if (prev != null)  // 如果链表非空，则将新节点连接到链表尾部
            prev.next = newNode;
        else  // 如果链表为空，则直接将新节点设为头节点
            array[index] = newNode;

        use_size++;
        if (Do_load_factor()) {
            resize();
        }
    }

    public void show() {
        for (int i = 0; i < array.length; i++) {
            System.out.print("Bucket " + i + ": ");
            Node cur = array[i];
            while (cur != null) {
                System.out.print("(" + cur.key + ", " + cur.val + ") -> ");
                cur = cur.next;
            }
            System.out.println("null");
        }
    }
}



